package ACwing.P2DataSturcture;

import java.io.*;

/**
 * @Date : 2023-03-08
 * @Description:
 */
public class KMP {
    //总串 s，长度M， 匹配串p，长度N，next[i]最长为N
    static int N=100010;
    static int M=1000010;
    static int n,m;
    static String P= "";
    static String S= "";
    static int[] ne=new int[N];
    static BufferedReader bf=new BufferedReader(new InputStreamReader(System.in));
    static StreamTokenizer st = new StreamTokenizer(bf);
    static PrintWriter pw=new PrintWriter(new OutputStreamWriter(System.out));
    public static void main(String[] args) throws IOException {
//        st.nextToken();
//        n= (int)st.nval;
        n= Integer.parseInt(bf.readLine());
        P=" "+bf.readLine();
        char [] p=P.toCharArray();
        st.nextToken();
        m= (int)st.nval;
        S = " "+bf.readLine();
        char [] s=S.toCharArray();
        /**
         * ne[]：存储一个字符串以每个位置为结尾的‘可匹配最长前后缀’的长度。
         * 构建ne[]数组：
         *              1,初始化ne[1] = 0,i从2开始。
         *              2,若匹配，s[i]==s[j+1]说明1~j+1是i的可匹配最长后缀,ne[i] = ++j;
         *              3,若不匹配，则从j的最长前缀位置+1的位置继续与i比较
         *              (因为i-1和j拥有相同的最长前后缀，我们拿j的前缀去对齐i-1的后缀),
         *              即令j = ne[j],继续比较j+1与i，若匹配转->>2
         *              4,若一直得不到匹配j最终会降到0，也就是i的‘可匹配最长前后缀’的长度
         *              要从零开始重新计算
         */

        //求next
        //这里从2开始是因为当第一个数时就是0所以不用参与。默认是0；
        for (int i = 2,j=0; i <=n; i++) {
            //这里判断从j是不是大于0，如果小于0，表示还没有前缀和后缀相等
            //如果出现下一个数与j+1这个数不相等就让j等于上一个数的next[];
            while(j!=0&&p[i]!=p[j+1]) j=ne[j];
            //如果j+1等于i这个数时候，就让j++，说明有有一个相等，前缀和后缀相等长度为1.
            if(p[i]==p[j+1]) j++;
            //然后将相等的缀长度存入next[]数组中；
            ne[i]=j;
        }

        /**
         * 匹配两个字符串：
         *      1，从i=1的位置开始逐个匹配，利用ne[]数组减少比较次数
         *      2，若i与j+1的位置不匹配（已知1~j匹配i-j~i-1)，
         *      j跳回ne[j]继续比较(因为1~j匹配i-j~i-1,所以1~ne[j]也能匹配到i-ne[j]~i-1)
         *      3，若匹配则j++,直到j==n能确定匹配成功
         *      4，成功后依然j = ne[j],就是把这次成功当成失败，继续匹配下一个位置
         */

        //kmp匹配过程
        for (int i = 1,j=0; i <=m; i++) {
            //判断j是不是大于0，小于0表示还没有前缀和后缀相等
            //判断长的数组一个一个遍历比较，看看短的数组，如果不相等就让j = 上一个数的缀长度
            while(j!=0&&s[i]!=p[j+1]) j=ne[j];
            //如果相等就让j++；继续进行下一个数的比较
            if(s[i]==p[j+1]) j++;
            //如果相等的数等于短的数组的长度，就说明该输出了
            if(j==n) {
                //匹配成功
                pw.write(i-n+" ");
                //输出之后，要继续往下面遍历对比，所以让j=上一个数的缀长度，
                //因为有前缀和后缀相等的部分可以重复使用
                j=ne[j];

            }

        }
        //所有write下的内容，会先存在writers中，当启用flush以后，会输出存在其中的内容。
        //如果没有调用flush，则不会将writer中的内容进行输出。
        pw.flush();
        bf.close();
        pw.close();

        /**
         * 时间复杂度：
         *      因为：j最多加m次，再加之前j每次都会减少且最少减一，j>0
         *      所以：while循环最多执行m次,若大于m次，j<0矛盾
         *      最终答案：O(2m)
         */
    }
/*  直接用String做
    public class Main {
        private static int[] nxt = new int[100010];
        static BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        static BufferedWriter log = new BufferedWriter(new OutputStreamWriter(System.out));

        public static void main(String[] args) throws IOException{
            int n = Integer.valueOf(reader.readLine());
            String p = " " + reader.readLine();
            int m = Integer.valueOf(reader.readLine());
            String s = " " + reader.readLine();

            for(int i = 2, j = 0; i <= n; i++) {
                while(j != 0 && p.charAt(j+1) != p.charAt(i)) j = nxt[j];
                if(p.charAt(j+1) == p.charAt(i)) j++;
                nxt[i] = j;
            }

            for(int i = 1, j = 0; i <= m; i++) {
                while(j != 0 && p.charAt(j+1) != s.charAt(i)) j = nxt[j];
                if(p.charAt(j+1) == s.charAt(i)) j++;
                if(j == n) { //成功
                    j = nxt[j]; //可能后面还有其他满足的情况，继续匹配
                    log.write(i-n + " ");
                }
            }

            log.flush();    // 关闭输入输出流
            reader.close();
            log.close();
        }
*/

}
